\section{Models for $k$-Gossip Problem}
\label{sec:models} 

The $k$-gossip problem in dynamic networks ia a fundamental problem in
distributed computing and is rich in terms of future research
directions. It can be studied in various models, with varying
difficulty and differing along different dimensions. We present a
discussion of the most important and interesting models. We structure
the discussion based on the different dimensions along which these
models differ, which also illustrates their power and weaknesses.

One of the most important dimension for k-gossip problems is the
adversarial model used. In general, we can consider three different
types of adversaries: {\em adaptive}, {\em oblivious} and {\em
  offline}.  An adaptive adversary can adapt to the steps of the
algorithm, and in particular, base its decisions on the current state
of token distribution while laying out the network. An oblivious
adversary, on the other hand, is required to lay out the entire
network sequece before the start of the protocol, which, however, is
revealed to the algorithm one at a time in successive rounds. The
above two adversaries are meaningful in the online setting of the
problem. An offline adversary, in contrast, not only lays out the
entire network sequence in advance, but this information is also
available to the algorithm before it starts.

The adaptive adversarial model can further be subdivided as strong,
intermediate or weak based on the order of execution of the steps of
the adversary and the algorithm in each round. In the strong adaptive
addversarial model, in each round and for each node, the algorithm is
first required to decide which token to broadcst from the set of
tokens it has obtained by the end of the previous round. The adversary
then lays out the network for the current round with the complete
knowledge of the token distribution till the end of the previous round
as well as all the choices made by the algorithm for the current
round. This is the strongest type of adversary and is the first model
studied in this paper. In contrast, in the weak adaptive adversarial
model, the adversary is first required to lay down the network for the
current round with the knowledge of the token distribution till the
end of the previous round, and this network is revealed to the
algorithm while making its decisions for the current round. In the
intermediate adaptive adversarial model, the adversary and the
algorithm are required to execute their steps in parallel. That is,
the adversary is required to lay down the network with the knowledge
of the token distribution till the end of the previous round but this
network is not revealed to the algorithm while making its choices for
the current round. This kind of adversary is intermediate between
strong and weak in its power, hence the name.

The oblivious adversarial model can be further classified as strong
or weak. While for both, the adversary lays out the entire netwrok
sequence in advance of the start of the protocol, the two differs in
when the algorithm is revealed the network for the current round. In
the case of strong oblivious adversarial model, in every round, the
algorithm is first decides which token to broadcast for each node from
the set of tokens it has till the end of the previous round. The
network for the current round is then revealed to it. In the weak
oblivious adversarial model, the network for the current round is
shown to the algorithm while making its decisions for the current
round.

Another dimension in which models for the $k$-gossip problem differ is
the broadcast Vs. multi-port model. In the broadcast model, every node
broadcast at most one token in each round which is received by all of
its neighbors. In contrast, the multi-port model allows each node to
send different tokens to different neighbors. Another dimension is the
use of randomness - the models can allow randomized algorithms or
restrict to deterministic ones.

We now list which combinations of different model dimensions make
sense. In both of the strong and intermediate adaptive adversarial
models, only broadcast algorithms makes sense and we can have both
deterministic or randomied kinds. It is worth noting that the strong
adaptive and intermediate adaptive models are the same when restricted
to deterministic algorithms, as the intermediate adaptive adversary
can always compute the decisions made by the algorithm in the current
round which essentially makes it a strong adaptive adversary. In the
weak adaptive adversarial model, both broadcast and multi-port
algorithms make sense, and both of the kind can be either deterministic
or randomized.

IN the strong oblivious adversarial model, only broadcast algorithms
make sense which can be either deterministic or randomized. In the
weak oblivious adversarial model and the offlie adversarial model, we
can have broadcast or multi-port algorithms and each kind can be
either deterministic or randomized. 

Our lower bound holds in the strong adaptive adversarial model against
deterministic as well as randomized broadcast algorithms. By the
equivalence between strong adaptive and intermediate adaptive models
for deterministic algorithms stated above, our lower bounds also
extend to intermediate adaptive adversarial model against
deterministic broadcast algorithms. We present a randomized multi-port
algorithm in the weak adaptive adversarial model where we start from a
well-mixed token distribution and assume the ability of $O(\log n)$
communication steps per round.





